Применение методов линейного программирования в задачах логистики

Введение

В настоящее время развитие современного общества постоянно требует повышения технического уровня, предъявляет всё более высокие требования к методам планирования и хозяйственного руководства. Поэтому обеспечить высокие темпы развития народного хозяйства позволит только научный подход к руководству экономической жизнью общества.
Дальнейшее развитие экономической науки невозможно без использования методов точного количественного анализа и широкого применения математических знаний, а управление народным хозяйством требует широкого применения математических методов и использования электронно-вычислительной техники в экономике.
Курсовая работа посвящена описанию основных методов линейного программирования, применяемых в задачах логистики. Линейное программирование является одним из наиболее разработанных разделов математической теории принятия оптимальных решений в различных областях экономики и поэтому знание и владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики. Появление линейного программирования было обусловлено бурным ростом в XX веке технического прогресса, связанного со второй мировой войной, который ставил перед наукой всё новые и новые задачи, требующие неукоснительного решения.

В английском языке слово «programming» означает планирование, составление планов или программ и это подчеркивает тесную связь между
линейным программированием и его экономической интерпретацией.
В свою очередь логистика представляет собой неотъемлемую часть современной экономики, основной задачей которой является управление её потоками. Логистика является действенным инструментом позволяющим реально сократить расходы на всех этапах промышленного цикла и с помощью этого получить конкурентное преимущество за счёт установления более низкой цены при сохранении качества товара или услуг. В целом ряде случаев проблему снижения издержек в конкретной области экономики можно свести к одной из моделей линейного программирования, а затем применив разработанные в этой теории математические методы получить оптимальное решение. Кроме этого, к моделям линейного программирования можно свести и целый ряд моделей другого типа.
Линейное программирование характеризуется тем, что оно позволяет находить экстремальные (наибольшие и наименьшие) значения линейной функции (называемой целевой функцией), неизвестные которой связаны линейными ограничениями (линейными уравнениями или линейными неравенствами). Эта особенность и объясняет термин «линейное программирование». Задачи линейного программирования являются задачами на условный экстремум.
К задачам линейного программирования относятся, например такие как:
- задачи рационального использования сырья и материалов;
- задачи оптимального раскроя;
- задачи оптимизации производственной программы предприятий;
- задачи оптимального размещения и концентрации производства;
- составления оптимального плана перевозок и работы транспорта (транспортные задачи);
- задачи управления производственными запасами;
- и другие задачи сферы оптимального планирования.
Методами решения задачи линейного программирования являются:
- графический метод;
- симплексный метод;
- двойственность в задачах линейного программирования;
- двойственный симплексный метод.
Экономико-математические модели являются представлениями логистической системы в математических терминах, которые позволяют использовать их вместо самой системы для исследования её свойств и прогнозирования её поведения.
Исследования громоздких моделей линейного программирования можно проводить с помощью специально разработанных компьютерных пакетов и электронных таблиц Excel.
Актуальность данной темы заключается в том, что на данной этапе формирования логистики как науки невозможно без применения ЭВМ и необходимый знаний в области экономико-математического моделирования. На практике использование и прогнозирование поведения логистических систем при тех или иных видах возмущающих и управляющих воздействий заменяется исследованием и прогнозированием поведения их моделей.
Объектом курсовой работы являются оптимизационные задачи логистики.
Предметом являются основные модели и методы линейного программирования, используемые для решения логистических задач.
Цель данной курсовой заключается в описании решения логистических задач методами линейного программирования и их иллюстрации на конкретных примерах, а также применении для этого модуля «Поиск решения» в Excel.
Модуль «Поиск решения» в Excel позволяет осуществлять поиск оптимальных решений задач линейного программирования, решение задач целочисленного и нелинейного программирования. Решения задач с помощью этого модуля выполняются с помощью задания ячеек для переменных и записи формул с использованием ячеек, выбранных для целевой функции и системы ограничений.
Задачи, поставленные в данной курсовой работе:
- описать основные понятия моделей линейного программирования;
- описать основные виды моделей, используемых в логистических задачах.
- описать графический метод решения задач линейного программирования и его алгоритм.
- описать симплекс-метод решения задач линейного программирования и указан алгоритм его применения.
- описать транспортную задачу и алгоритм её решения.
- описать применение модуля «Поиск решения» MS Excel для решения задач линейного программирования.

1 Теоретическая часть
Основные методы решения задач линейного программирования

1.1 Постановка задач линейного программирования

Задачи линейного программирования являются задачами на определение максимума или минимума некоторой линейной функции n переменных Z=∑_(j=1)^n▒〖c_j x_j 〗=c_1 x_1+⋯+c_n x_n+c_0, переменные x_1,…,x_n которой удовлетворяют системе линейных ограничений следующего вида:
∑_(j=1)^n▒〖a_ij x_j≤b_i (i=(1,m_1 ) ̅ ) 〗j=1naijxj=bi i=m1+1,m2j=1naijxj≥bi i=m2+1,mx_j≥0 (j=(1,n) ̅ )
Такая форма записи задачи линейного программирования называется её общей формой.
Задачи линейного программирования, которые задаются условиями:
Z=∑_(j=1)^n▒〖c_j x_j 〗→max Z=∑_(j=1)^n▒〖c_j x_j 〗→min
∑_(j=1)^n▒〖a_ij x_j≤b_i (i=(1,m) ̅ ) 〗xj≥0 j=1,n {█(∑_(j=1)^n▒〖a_ij x_j≥b_i (i=(1,m) ̅ ) 〗@x_j≥0 (j=(1,n) ̅ ) )┤
называются задачами, заданными в стандартной форме.
Задачи линейного программирования, которые задаются условиями:
Z=∑_(j=1)^n▒〖c_j x_j 〗→max
{█(∑_(j=1)^n▒〖a_ij x_j=b_i (i=(1,m) ̅ ) 〗@x_j≥0 (j=(1,n) ̅ ) )┤
называются задачами, заданными в канонической форме.
Указанные выше три формы записи ЗЛП эквивалентны так как каждая из них с помощью простых преобразований сводится к другой форме, другими словами, если найдено оптимальное решение задачи в одной из перечисленных форм, то можно определить оптимальный план задачи заданной в любой другой форме.
Например, так как maxZ(X)=minZ(-X), то задачу максимизации можно заменить задачей минимизации, и наоборот.
Неравенство типа ≤ путем умножения его левых и правых частей на -1 можно превратить в неравенство типа ≥ и наоборот.
Ограничения-неравенства с помощью прибавления или вычитания дополнительных переменных можно преобразовать в ограничения-равенства.
Ограничение-равенство a_i1 x_1+⋯+a_in x_n=b_i можно представить в виде системы неравенств вида

{█(a_i1 x_1+⋯+a_in x_n≥b_i@a_i1 x_1+⋯+a_in x_n≤b_i )┤.

Построение модели линейного программирования соответствующей некоторой задаче логистики можно осуществить по следующей схеме:
1. Определяем набор переменных, которые описывают процесс принятия решений. Эти переменные, в дальнейшем называем параметрами управления.
2. Определяем целевую функцию, соответствующую решаемой задаче логистики и зависящую от параметров управления.
3. Учитывая условие решаемой задачи, составляем систему необходимых ограничений.
Рассмотрим пример задачи об использовании ресурсов.
Предприятие выпускает три вида продукции П1, П2, П3 и имеет в своем распоряжении ресурсы трех видов R1, R2, R3 соответственно в количестве 20, 25, 30 условных единиц. В таблице 1 указано количество единиц ресурсов, которые затрачиваются на изготовление единицы выпускаемой продукции, а также прибыль, которая получается от реализации единицы продукции.
Таблица 1

Ресурсы Виды изделий
П1 П2 П3
R1 2 4 2
R2 4 2 3
R3 3 1 2
Прибыль, одной единицы продукции, ден. ед. 2 3 4






Требуется составить такой план производства продукции, при котором прибыль предприятия, при заданных ресурсах, оказалась бы максимальной.
Построим экономико-математическую модель данной задачи логистики.
Введем набор управляющих переменных. Обозначим через x1, x2, x3
соответственно количество продукции вида П1, П2, П3.
Общее количество ресурсов R1, R2, R3, используемых при выпуске трех видов продукции, не должно превосходить запаса, то есть:

{█(2x_1+4x_2+2x_3≤20@4x_1+2x_2+3x_3≤25@3x_1+x_2+2x_3≤30)┤

По смыслу задачи переменные неотрицательны:

x_1≥0, x_2≥0, x_3≥0.

Из условия задачи следует, что прибыль предприятия от реализации произведённой продукции составит 〖2x〗_1+3x_2+4x_3 ден. ед.
В результате получаем следующую экономико-математическую модель данной логистической задачи:
Требуется найти такой план выпуска продукции x1, x2, x3, который удовлетворяет системе линейных ограничений

{█(2x_1+4x_2+2x_3≤20@4x_1+2x_2+3x_3≤25@3x_1+x_2+2x_3≤30@x_1≥0,x_2≥0,x_3≥0)┤

и придаёт целевой функции Z=〖2x〗_1+3x_2+4x_3 максимальное значение.

1.2 Графическое решение задачи линейного программирования

Каждую ЗЛП, заданную в стандартной форме с двумя переменными, можно решить графическим методом. В такой задаче система ограничений и целевая функция имеют следующий вид:
Целевая функция
Z=c_1 x_1+c_2 x_2,
а система ограничений
{█(a_11 x_1+a_12 x_2≤b_1@a_21 x_1+a_22 x_2≤b_2@………………………@a_m1 x_1+a_m2 x_2≤b_m@x_1≥0,x_2≥0)┤

Любое неравенство системы ограничений такой ЗЛП определяет на координатной плоскости x_1 Ox_2 полуплоскость и границами этих полуплоскостей служат прямые a_11x_1+a_12 x_2=b_1, a_21 x_1+a_22 x_2=b_2, …, a_m1 x_1+a_m2 x_2=b_m, а условия неотрицательности переменных задают полуплоскости границами которых являются прямые x_1=0 и x_2=0.
Если система ограничений является совместной, то она имеет по крайней мере одно решение и в таком случае множество её решений задаёт на координатной плоскости некоторое выпуклое множество точек, называемое многоугольником решений или областью (множеством) допустимых решений. Такое множество может являться точкой, отрезком или лучом, выпуклым многоугольником или неограниченной многоугольной областью.
Каждая угловая точка многоугольника решений называется допустимым базисным решением.
Справедлива следующая теорема.
Теорема 1. Если задача линейного программирования имеет
оптимальное решение, то целевая функция достигает своего экстремального
значения в угловой точке многоугольника решений.
При графическом методе решения подобной ЗЛП можно придерживаться следующего алгоритма.
1. Составляем экономико-математическую модель данной задачи.
2. Строим на координатной плоскости x_1 Ox_2 область допустимых решений и если она является пустым множеством, то задача не имеет решений, а в противном случае переходим к следующему пункту алгоритма.
3. По целевой функции Z=c_1 x_1+c_2 x_2 cтроим её вектор-градиент (OC) ⃗, где O(0;0),C(c_1;c_2).
Этот вектор перпендикулярен линии уровня c_1 x_1+c_2 x_2=0.
4. Через точку O(0;0) проводим прямую перпендикулярную вектору-градиенту и параллельным перемещением, в случае поиска maxZ, в направлении вектора-градиента ищем последнюю общую точку этой прямой с областью допустимых решений. Координаты этой точки и дают искомое максимум целевой функции.
Если необходимо найти minZ, параллельный перенос линии уровня осуществляем в направлении противоположном вектору-градиенту и ищем её последнюю общую точку с областью допустимых решений. Координаты этой точки и будут определять искомый минимум целевой функции.


Рассмотрим пример задачи на составления рациона.
При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества S1, 8 ед. питательного вещества S2 и 12 ед. питательного вещества S3. Для составления рациона используют два вида корма К1 и К2. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 2.
Требуется составить дневной рацион нужной питательности, причем
затраты на него должны быть минимальными.
Таблица 2

Питательные вещества Количество единиц питательных веществ в 1кг корма
K1 K2
S1 2 4
S2 4 2
S3 3 1
Стоимость 1 кг. корма, ден. ед. 2 3

1. Построим экономико-математическую модель данной задачи логистики.
Введем набор управляющих переменных. Обозначим через x1, x2,
соответственно, количество килограммов корма К1, К2 дневного рациона животных.
Общее количество питательных веществ S1, S2, S3, входящих в рацион питания животных, должно быть не меньше требуемого их минимума, т. е.:

{█(2x_1+4x_2≥9@4x_1+2x_2≥8@3x_1+x_2≥12)┤

Также, по смыслу задачи переменные должны быть неотрицательными:

x_1≥0, x_2≥0.

Из условия задачи следует, что затраты на обеспечение такого рациона составят 〖2x〗_1+3x_2 ден. ед.
В результате получаем следующую экономико-математическую модель данной логистической задачи:
Требуется найти такой план x1, x2, закупки килограмм корма К1, К2, который удовлетворяет системе линейных ограничений
{█(2x_1+4x_2≥9@4x_1+2x_2≥8@3x_1+x_2≥12@x_1≥0,x_2≥0)┤

и придаёт целевой функции Z=〖2x〗_1+3x_2 минимальное значение.
2. Строим на координатной плоскости x_1 Ox_2 область допустимых решений данной задачи (рис. 1).